package my.jwds.p427;

import com.alibaba.fastjson.JSONObject;

public class Construct {

    public static void main(String[] args) {

        Solution1 obj = new Solution1();
        int [][]grid = JSONObject.parseObject("[[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]",int[][].class);
        long start = System.currentTimeMillis();
        obj.construct(grid);
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    static class Solution {
        int[][] grid ;

        public Node construct(int[][] grid) {
            int n = grid.length;
            this.grid = grid;
            return dfs(0,n,0,n);
        }

        public Node dfs(int y1,int y2,int x1,int x2){
            int temp = grid[y1][x1];

            for (int i = y1; i < y2; i++) {
                for (int j = x1; j < x2; j++) {
                    if (temp != grid[i][j]){
                        int v = (y2 - y1)/2;
                        return new Node(false,false
                                ,dfs(y1,y1+v,x1,x1+v)
                                ,dfs(y1,y1+v,x1+v,x2)
                                ,dfs(y1+v,y2,x1,x1+v)
                                ,dfs(y1+v,y2,x1+v,x2)
                        );
                    }
                }
            }
            return new Node(temp == 1,true);
        }
    }
    static class Solution1 {
        int[][] grid ;
        int[][] sum;
        public Node construct(int[][] grid) {
            int n = grid.length;
            this.grid = grid;
            sum = new int[n+1][n+1];
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + grid[i-1][j-1];
                }
            }


            return dfs(0,n,0,n);
        }

        public Node dfs(int y1,int y2,int x1,int x2){
            System.out.println("["+y1+","+x1+"] | ["+y2+","+x2+"]");
            int res = getSum(y1, y2, x1, x2);
            if (res == 0 || res == (y2-y1)*(x2-x1)){
                return new Node(grid[y1][x1] == 1,true);
            }else{
                int v = (y2 - y1)/2;
                return new Node(false,false
                        ,dfs(y1,y1+v,x1,x1+v)
                        ,dfs(y1,y1+v,x1+v,x2)
                        ,dfs(y1+v,y2,x1,x1+v)
                        ,dfs(y1+v,y2,x1+v,x2)
                );
            }
        }

        int getSum(int y1,int y2,int x1,int x2){
            return sum[y2][x2] - sum[y2][x1] - sum[y1][x2] + sum[y1][x1];
        }
    }

    static class Node {
        public boolean val;
        public boolean isLeaf;
        public Node topLeft;
        public Node topRight;
        public Node bottomLeft;
        public Node bottomRight;


        public Node() {
            this.val = false;
            this.isLeaf = false;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = topLeft;
            this.topRight = topRight;
            this.bottomLeft = bottomLeft;
            this.bottomRight = bottomRight;
        }
    };
}